package com.hucsmn.lcs;

import java.util.Scanner;

/**
 * 作业题二：
 * 编程获取两个指定字符串中的最大相同子串。
 * 如： s1="asdafghjka", s2="aaasdfg" 他们的最大子串为"asd"
 * 提示： 将短的那个串进行长度依次递减的子串与较长的串比较。
 */
public class LongestCommonSubstring {
    private static final String NEWLINE = System.lineSeparator();

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (true) {
            String s0, s1;
            try {
                System.out.print("输入第一个字符串：");
                s0 = preprocess(sc.nextLine());
                System.out.print("输入第二个字符串：");
                s1 = preprocess(sc.nextLine());
            } catch (IllegalArgumentException ex) {
                System.out.println("输入不合法！");
                continue;
            }

            String lcs = naiveLcs(s0, s1);
            System.out.println("一个最大相同子串为：" + lcs);
        }
    }

    /**
     * 穷举法查找两段文本中的最大公共子串，支持 Unicode。
     *
     * @param s0 第一个字符串，假设是正确的 UTF-16 编码。
     * @param s1 第二个字符串，假设是正确的 UTF-16 编码。
     * @return 其中一个最大公共子串。
     */
    public static String naiveLcs(String s0, String s1) {
        // 已知的最长公共子串的下界。
        int knownMax = 0;
        String knownLcs = "";

        for (int n = Integer.min(s0.length(), s1.length()); n > knownMax; n--) {
            // 穷举特定编码长度的子串。
            for (int i = 0; i <= s0.length() - n; i++) {
                // 测试子串是否是正确的 UTF-16 字符串，且是一个公共子串，满足条件则继续判断。
                String sub = s0.substring(i, i + n);
                if (Character.isLowSurrogate(sub.charAt(0))
                        || Character.isHighSurrogate(sub.charAt(n - 1))
                        || !s1.contains(sub)) {
                    continue;
                }

                // 不包含辅助平面字符时，可以直接断定找到了一个最长公共子串。
                int m = sub.codePointCount(0, n);
                if (m == n) {
                    return sub;
                }

                // 否则只能确定找到了最长公共子串的一个下界，修改终止条件。
                if (m > knownMax) {
                    knownMax = m;
                    knownLcs = sub;
                }
            }
        }

        // 已知的下界一定是一个最长公共子串。
        return knownLcs;
    }

    /**
     * 去除输入行末尾的换行符，并验证输入是否合法。
     *
     * @param line 输入的行。
     * @return 去除最后一个换行符的输入。
     * @throws IllegalArgumentException 输入的字符串不是合法的 UTF-16 字符串。
     */
    private static String preprocess(String line) throws IllegalArgumentException {
        // 去除换行符。
        if (line.endsWith(NEWLINE)) {
            line = line.substring(0, line.length() - NEWLINE.length());
        }

        // 验证 UTF-16 编码。
        boolean prevhs = false;
        for(int i = 0; i < line.length(); i++) {
            char ch = line.charAt(i);
            if (Character.isHighSurrogate(ch)) {
                if (prevhs) {
                    throw new IllegalArgumentException();
                }
                prevhs = true;
            } else if (Character.isLowSurrogate(ch)) {
                if (!prevhs) {
                    throw new IllegalArgumentException();
                }
                prevhs = false;
            } else if (prevhs) {
                throw new IllegalArgumentException();
            }
        }
        if (prevhs) {
            throw new IllegalArgumentException();
        }

        return line;
    }
}
